package array.nsum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NSum {

    /**
     * 注意：调用该函数前，必须先调用一次sort方法对数组进行排序
     * @param nums
     * @param n 想要求得的是几数之和
     * @param start 开始索引，默认为0
     * @param target 目标值
     * @return
     */
    public List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target) {

        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 至少是2sum，且数组大小不能小于n
        if (n < 2 || len < n) {return res;}
        // 2sum,base case
        if (n == 2) {
            int lo = start;
            int hi = len - 1;
            while (lo < hi) {
                int left = nums[lo];
                int right = nums[hi];
                int sum = left + right;
                if (sum < target) {
                    while (lo < hi && nums[lo] == left) lo++;
                } else if (sum > target) {
                    while (lo < hi && nums[hi] == right) hi--;
                } else {
                    res.add(Arrays.asList(left, right));
                    while (lo < hi && nums[lo] == left) lo++;
                    while (lo < hi && nums[hi] == right) hi--;
                }
            }
        } else {
            // n > 2时，递归计算(n-1)Sum
            for (int i = start; i < len; i++) {
                List<List<Integer>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> list : sub) {
                    list.add(nums[i]);
                    res.add(list);
                }
                // 跳过第一个元素
                while (i < len - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }
}
